package com.wfs.suanfa.leet;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class LRUCache2<K,V> {
    static class Entry<K,V>{
        public Entry<K, V> prev;
        public Entry<K, V> next;
        public K key;
        public V val;
        public Entry() {}
        public Entry(K key, V val) { this.key = key; this.val = val; }
    }

    private Entry<K, V> head, tail; // 虚拟头节点和虚拟尾节点
    private  int capacity;     // 缓存容量
    private int size;               // 缓存占用量
    Map<K,Entry<K, V>> cache;      // 哈希表，记录双向列表节点的地址值

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        cache=new HashMap<>(capacity);
    }

    public void put(K key,V val){
        Entry<K, V> entry = cache.get(key);
        if (Objects.nonNull(entry)){
            //从当前位置删除 移动到头结点
        }else {
            //执行插入
            if (size== capacity){
                //删除尾节点
                cache.remove(tail.key);
                tail.prev.next=null;
                tail=tail.prev;
                size--;
            }
            Entry<K, V> entry1 = new Entry<>(key, val);
            //插入节点到头部
            addEntry(entry1);
            cache.put(entry1.key,entry1);
            size++;
        }
    }
    public Entry<K,V> get(K key){
        Entry<K, V> entry = cache.get(key);
        if (Objects.isNull(entry)){
            return null;
        }
        delEntry(entry);
        cache.remove(entry.key,entry);
        Entry<K, V> entry1 = new Entry<>(entry.key, entry.val);
        addEntry(entry1);
        cache.put(entry1.key,entry1);
        return entry1;
    }

    private void delEntry(Entry<K, V> entry) {
        if (Objects.isNull(entry)){
            return;
        }
        if (Objects.equals(entry,head)){
            head=head.next;
            head.prev=null;
        }else if (Objects.equals(entry,tail)){
            tail=tail.prev;
            tail.next=null;
        }else {
            entry.next.prev=entry.prev;
            entry.prev.next=entry.next;

        }
    }

    /**
     * 头插
     */
    private void addEntry(Entry<K, V> entry) {
        if (Objects.isNull(entry)){
            return;
        }
        if (Objects.isNull(head)){
            head=entry;
            tail=head;
        }else {
            entry.next=head;
            head.prev=entry;
            head=entry;
        }

    }

    public static void main(String[] args) {
        LRUCache2<Integer, String> cache = new LRUCache2<>(3);
        cache.put(1,"可口可乐");
        cache.put(2,"雪碧");
        System.out.println("页面1的内容：" + cache.get(1).val);
        cache.put(3,"果粒橙"); // 此时缓存已满，且页面2最久未被使用（因为cache.get(1)访问了页面1），页面2被置换成页面3
        cache.put(4,"怡宝");
        System.out.println("页面2的内容：" + cache.get(3)); // 页面2已被换出，访问不到
        System.out.println("页面2的内容："); // 页面2已被换出，访问不到
    }
}
